package c_leetcode.a_70_climbing_stairs;

/**
 * 递归解决
 * 时间复杂度    O(2^n)
 * 空间复杂度    O(n)
 * ------
 * 缺点：n过大时，计算时间过长
 * 2^0  climbStairs(n) =
 * 2^1  climbStairs(n-1) + climbStairs(n-2) =
 * 2^3  climbStairs(n-2) + climbStairs(n-3) + climbStairs(n-3) + climbStairs(n-4)
 * ...
 * 2^(n-1) climbStairs(1) + ......
 * ------
 * 时间复杂度=循环次数=2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(n-1)
 * 2^10=1024(千级)    2^20(百万级)   2*30(十亿级)，LeetCode 将会超时
 *
 * @author FRSF
 * @since 2025/2/20 22:31
 */
public class Recursion {

    public static void main(String[] args) {
        Recursion recursion = new Recursion();
        System.out.println(recursion.climbStairs(5));
    }

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}
